package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 将数组拆分成斐波那契序列
 */

public class Code842 {
    public static void main(String[] args) {
        String num = "1101111";
        System.out.println(new Code842().splitStringToFindFibonacci(num));
    }

    public List<Integer> splitStringToFindFibonacci(String num) {
        List<Integer> result = new ArrayList<>();
        backtrack(num, 0, result);
        return result;
    }

    private boolean backtrack(String num, int start, List<Integer> result) {
        if (result.size() >= 3 && start == num.length()) {
            return true;
        }

        for (int end = start + 1; end <= num.length(); end++) {
            String part = num.substring(start, end);

            // 剪枝：前导零的情况
            if (part.length() > 1 && part.charAt(0) == '0') {
                return false;
            }

            // 剪枝：超过 Integer.MAX_VALUE 的值
            long value = 0;
            try {
                value = Long.parseLong(part);
                if (value > Integer.MAX_VALUE) {
                    return false;
                }
            } catch (NumberFormatException e) {
                return false;
            }

            int size = result.size();
            // 如果已经有至少两个数，检查是否符合斐波那契规则
            if (size >= 2 && (long) result.get(size - 1) + (long) result.get(size - 2) != value) {
                continue;
            }

            result.add((int) value);
            if (backtrack(num, end, result)) {
                return true;
            }
            result.remove(result.size() - 1);
        }

        return false;
    }
}
